#include <iostream>
#include <stack>

#include <omp.h>

#include "ogsolverBBPv4openMP.h"

/**
 * A BBP solver : starts with jobs with last due dates
 *
 * Dans cette version 3 de la BBP, on demarre avec les jobs reordonnes dans le sens des dates dues croissantes. Mais
 * contrairement a l'exploration brutale de la version 2, cette fois on ne considere pas n'importe quel numero de batch.
 * Pour chaque job, on choisit de le rajouter soit dans un batch deja existant dont la capacite residuel est suffisante
 * pour stocker le nouveau job, soit dans un nouveau batch.
 *
 * Le nouveau batch est ordonnance avant les autres batchs deja crees.
 *
 * ATTENTION : Pour que cette solution soit optimale, sachant que l'on
 * part d'un probleme pour lequel les jobs sont classes par date due croissante, il est egalement necessaire que le cout de stockage
 * de tous les jobs soient identiques. Dans le cas contraire, la solution ainsi construite n'est plus certaine d'etre optimale.
 */
OGSolverBBPv4openMPiterative::OGSolverBBPv4openMPiterative(GSupplyLinkProblem& pb):OGSolverBBPv3(pb) {
}

OGSolverBBPv4openMPiterative::~OGSolverBBPv4openMPiterative() {
//    if (this->bestSolution != NULL ) delete this->bestSolution ;
//    if (this->bestSolutionDueDateOrdered != NULL ) delete this->bestSolutionDueDateOrdered ;
//    if (this->currentSolutionDueDateOrdered != NULL ) delete this->currentSolutionDueDateOrdered ;
}

/**
 *
 */
void OGSolverBBPv4openMPiterative::solveMain() {
    cout << "BBPv4 OpenMP iterative" << endl ;

//    vector<double> tabBatchRemainingCapacity(maxBatch) ;
//    for (int b=0;b<maxBatch;b++)
//        tabBatchRemainingCapacity[b] = this->problem.getTransporter(0).getCapacity() ;

    // Root node : create a batch with the last job
    searchnode rootNode ;
    rootNode.nbrbatch = 1 ;
    rootNode.job = this->problem.getNP()-1 ;
    rootNode.sol = this->currentSolutionDueDateOrdered ;
    rootNode.tabBatchRemainingCapacity.insert(rootNode.tabBatchRemainingCapacity.begin(),this->problem.getTransporter(0).getCapacity()) ;
    rootNode.tabBatchRemainingCapacity[0] -= this->problem.getJobSize(rootNode.job) ;
    rootNode.sol.setBatchIndice(rootNode.job, 1) ;
    rootNode.sol.setDeliveryCompletionTime(rootNode.job, (double)1.0) ;
    rootNode.sol.setNbrBatch(1) ;
    mystack.push(rootNode) ;

    // Multi processes
    cout << "depthFirstSearchMulti() started" << endl ;
    depthFirstSearchMultiIterative() ;

}

/**
 * DepthFirstSearch (BBP) with multi processes (Parallel with openMP)
 */
searchnode OGSolverBBPv4openMPiterative::generateChildNode(const searchnode& currentNode, int batchPotentialIndice) {
    // private local variables => openMP
    int batchRealIndice=-1 ;
    int incnbrbatch = -1 ;
    int job2 ;

    // Job is added to an existing batch
    if (batchPotentialIndice>=0 && currentNode.tabBatchRemainingCapacity[batchPotentialIndice]>=this->problem.getJobSize(currentNode.job)) {
        batchRealIndice= batchPotentialIndice ;
        incnbrbatch = 0 ;
    }

    // Creation of a new batch
    if (batchPotentialIndice<0) {
        batchRealIndice=0 ;
        incnbrbatch = 1 ;
    }

    searchnode childnode (currentNode) ;

    childnode.nbrbatch = -1 ;

    // Transformation of the solution
    if (incnbrbatch>=0) {
        //childnode.tabBatchRemainingCapacity = currentNode.tabBatchRemainingCapacity ;
        //childnode.sol = currentNode.sol ;

        if (incnbrbatch>0) {
            childnode.tabBatchRemainingCapacity.insert(childnode.tabBatchRemainingCapacity.begin(),this->problem.getTransporter(0).getCapacity()) ;
            // The batch indices of previously placed jobs should be increased
            for (job2=currentNode.job+1;job2<problem.getNP();job2++) {
                childnode.sol.setBatchIndice(job2,1+childnode.sol.getBatchIndice(job2)) ;
            }
        }
        childnode.tabBatchRemainingCapacity[batchRealIndice] -= this->problem.getJobSize(currentNode.job) ;
        childnode.sol.setBatchIndice(currentNode.job, batchRealIndice+1) ;
        childnode.sol.setDeliveryCompletionTime(currentNode.job, (double)batchRealIndice+1) ;
        childnode.sol.setNbrBatch(currentNode.nbrbatch+incnbrbatch) ;
        childnode.nbrbatch = currentNode.nbrbatch+incnbrbatch ;
    }

    return childnode ;
}

/**
 * DepthFirstSearch (BBP) with multi processes (Parallel with openMP)
 */
void OGSolverBBPv4openMPiterative::depthFirstSearchMultiIterative() {

    int encore = 1 ;

    // private local variables => openMP
    int batchPotentialIndice = 0 ;
    double lowerBound ;
    int stoprecurs ;
    searchnode currentNode,childNode ;

    while (mystack.size()>0) {
        #pragma omp critical
        {
            currentNode = this->mystack.top() ; this->mystack.pop() ;
        }
        lowerBound = currentNode.sol.evaluatePartial(currentNode.job, this->problem.getNP()-1);
        assert (lowerBound>=0) ;

        stoprecurs=0 ;
        // Evaluation of the newly built solution
        if (currentNode.job<=0) {
            currentNode.sol.evaluate() ;
            if (bestSolutionDueDateOrdered.getEvaluation()<0 || currentNode.sol.getEvaluation()<bestSolutionDueDateOrdered.getEvaluation()) {
                #pragma omp critical
                {
                    bestSolutionDueDateOrdered = currentNode.sol ;
cout << "besteval=" << bestSolutionDueDateOrdered.getEvaluation() << endl ;
                }
            }
            stoprecurs=1 ;
        }

        // Cut
        if (!stoprecurs) {
            currentNode.job-- ;

            if (currentNode.nbrbatch<10) {
                for (batchPotentialIndice=-1;batchPotentialIndice<currentNode.nbrbatch;++batchPotentialIndice) {
                    if (lowerBound<bestSolutionDueDateOrdered.getEvaluation()) {
                        childNode = generateChildNode(currentNode,batchPotentialIndice) ;
                        if (childNode.nbrbatch>0) {
                            #pragma omp critical
                            {
                                mystack.push (childNode) ;
        //cout << "proc " << omp_get_thread_num() << " => mystack.size()=" << mystack.size() << endl ;
                            }
                        }
                    }
                }
            }
            else {

                #pragma omp parallel for shared(lowerBound,currentNode) private (batchPotentialIndice,childNode) schedule(dynamic)
                for (batchPotentialIndice=-1;batchPotentialIndice<currentNode.nbrbatch;++batchPotentialIndice) {
                    if (lowerBound<bestSolutionDueDateOrdered.getEvaluation()) {
                        childNode = generateChildNode(currentNode,batchPotentialIndice) ;
                        if (childNode.nbrbatch>0) {
                            #pragma omp critical
                            {
                                mystack.push (childNode) ;
        //cout << "proc " << omp_get_thread_num() << " => mystack.size()=" << mystack.size() << endl ;
                            }
                        }
                    }
                }
            }
        }
    }

}

/**
 *
 */
void OGSolverBBPv4openMPiterative::informationOpenMP() {
    int nthreads=0;             // number of thread available
    int threadid=0;             // id of thread
    // Information about parallelization
    #pragma omp parallel private(threadid)              // parallel region
    {
        #pragma omp master                              // only the master thread will execute this code
        {
            nthreads=omp_get_num_threads();             // computation of the total number of threads
            cout<<endl<<nthreads<<" thread(s) available for computation"<<endl;
        }

        #pragma omp barrier                             // barrier to display nthreads before threadid

        threadid=omp_get_thread_num();
        #pragma omp critical                            // in order to "protect" the common output
        {
            cout<<"Thread "<<threadid<<" is ready for computation"<<endl;
        }
    }
}

/**
 *
 */
ostream& operator<<(ostream& os,const searchnode& sn) {
        //int nbrbatch ; // number of batches
        //int job ;      // job to place
        //vector<double> tabBatchRemainingCapacity ;
        //OGSupplyLinkSolutionPartial sol ;
    os << "searchnode=[nbrbatch=" << sn.nbrbatch << ", " ;
    os << "job=" << sn.job << ", " ;
    os << "tabBatchRemainingCapacity=[" ;
    for (int i=0;i<sn.tabBatchRemainingCapacity.size();++i) {
        os << sn.tabBatchRemainingCapacity[i]  ;
        if (i<sn.tabBatchRemainingCapacity.size()-1) os << ", " ;
    }
    os << "], sol=" << sn.sol << "]" ;

    return os ;
}


